/**
 * 
 * 统计一个数字在排序数组中出现的次数。
 */

let nums = [5, 7, 7, 8, 8, 10];
let target = 8;


/**
 * 1. 暴力循环 
 * 时间复杂度 O(N), 空间复杂度 O(1)
 * 缺点： 没有充分利用数组有序的条件
 */

let search1 = function(nums, target) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            count++;
        }
    }
    return count;
};


/**
 * 二分法
 * 时间复杂度 O(logN), 空间复杂度 O(1)
 * 算法解析：
 * 初始化： 左边界 i = 0，右边界 j = len(nums) - 1 。
 * 循环二分： 当闭区间 [i, j] 无元素时跳出；
 * 计算中点 m = (i + j) / 2 （向下取整）；
 * 若 nums[m] < target ，则 target 在闭区间 [m + 1, j] 中，因此执行 i = m + 1；
 * 若 nums[m] > target ，则 target 在闭区间 [i, m - 1]中，因此执行 j = m - 1；
 * 若 nums[m] = target ，则右边界 right 在闭区间 [m+1, j] 中；左边界 leftleft 在闭区间 [i, m-1] 中。因此分为以下两种情况：
 * 若查找 右边界 right ，则执行 i = m + 1 ；（跳出时 i 指向右边界）
 * 若查找 左边界 left ，则执行 j = m - 1；（跳出时 j 指向左边界）
 * 返回值： 应用两次二分，分别查找 right 和 left ，最终返回 right - left - 1 即可。
 */

let search2 = function(nums, target) {
    let [i, j, m, left, right] = [0, nums.length - 1, 0, 0, 0];
    // 第一次二分：找right边界
    while (i <= j) {
        m = Math.floor((i + j) / 2);
        if (nums[m] <= target) {
            i = m + 1;
        } else {
            j = m - 1;
        }
    }
    right = i;
    if (j >= 0 && nums[j] !== target) {
        return 0;
    }
    i = 0;
    //第二次二分：找left边界
    while (i <= j) {
        m = Math.floor((i + j) / 2);
        if (nums[m] >= target) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    left = j;
    return right - left - 1;
};


/**
 * 简化二分法
 */

let search3 = function(nums, target) {
    function find(targ) {
        let [i, j, m] = [0, nums.length - 1, 0];
        while (i <= j) {
            m = Math.floor((i + j) / 2);
            if (nums[m] <= targ) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }
    return find(target) - find(target - 1);

}

// 算法测试
let resp = search2(nums, target);
console.log(resp);